package jun;

import java.util.Arrays;

/**
 * @author ：冯涛滔
 * @date ：Created in 2020-6-22 10:01
 * @description：
 * @modified By：
 * @version:
 */
public class Jun22 {
    /**
     * create by: 冯涛滔
     * description: https://leetcode-cn.com/problems/minimum-cost-for-tickets/ 983. 最低票价
     * create time: 2020-6-22 10:01
     *
     * @return int
     * @params [days, costs]
     */
    public int mincostTickets(int[] days, int[] costs) {
        int len = days.length;
        int maxDay = days[len - 1];
        int minDay = days[0];
        int[] dp = new int[maxDay + 31]; // 多扩几天，省得判断 365 的限制
        // 只需看 maxDay -> minDay，此区间外都不需要出门，不会增加费用
        for (int d = maxDay, i = len - 1; d >= minDay; d--) {
            // i 表示 days 的索引
            // 也可提前将所有 days 放入 Set，再通过 set.contains() 判断
            if (d == days[i]) {
                dp[d] = Math.min(dp[d + 1] + costs[0], dp[d + 7] + costs[1]);
                dp[d] = Math.min(dp[d], dp[d + 30] + costs[2]);
                i--; // 别忘了递减一天
            } else dp[d] = dp[d + 1]; // 不需要出门
        }
        return dp[minDay]; // 从后向前遍历，返回最前的 minDay
    }

    public int findLength(int[] A, int[] B) {
        int res = 0;
        int[][] record = new int[A.length + 1][B.length + 1];
        for (int i = 1; i <= A.length; i++) {
            for (int j = 1; j <= B.length; j++) {
                if (A[i - 1] == B[j - 1]) {
                    record[i][j] = record[i - 1][j - 1] + 1;
                }
                res = Math.max(res, record[i][j]);
            }
        }
        return res;
    }

    /**
     * create by: 冯涛滔
     * description: https://leetcode-cn.com/problems/number-of-longest-increasing-subsequence/submissions/
     * 从前往后记录以dp[i]也就是以nums[i]结尾的最长递增字串的长度
     * 如果不能形成更长的递增就看他们dp[j]和dp[i]的最长长度是否一致
     * 倒序遍历
     * create time: 2020-6-22 10:48
     *
     * @return int
     * @params [nums]
     */
    public int findNumberOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int n = nums.length;
        int[] dp = new int[n];
        int[] counter = new int[n];
        Arrays.fill(dp, 1);
        Arrays.fill(counter, 1);
        int max = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    if (dp[j] + 1 > dp[i]) {
                        dp[i] = Math.max(dp[i], dp[j] + 1);
                        counter[i] = counter[j];
                    } else if (dp[j] + 1 == dp[i]) {
                        counter[i] += counter[j];
                    }
                }
            }
            max = Math.max(max, dp[i]);
        }
        int res = 0;
        for (int i = 0; i < n; i++) {
            if (dp[i] == max) res += counter[i];
        }
        return res;
    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }
    public int max = 0;
    public long res = 0;
    public int getNum(TreeNode root){
        if(root==null)
            return 0;
        return root.val + getNum(root.left) + getNum(root.right);
    }

    public int maxProduct(TreeNode root) {
        max = getNum(root);
        a(root);
        return (int) (res%(1e9+7));
    }
    public void a(TreeNode root){
        if(root==null){
            return;
        }
        //以这个节点作为计算删除左右边的乘积
        int left = getNum(root.left);
        int right = getNum(root.right);
        int a  = Math.max((max-left)*left,(max-right)*right);
        res =  Math.max(res,a);
        a(root.right);
        a(root.left);

    }
    public int maxProfit(int[] prices) {
        int preMoney = 0;
        int prePro  = prices[0];
        for (int i = 1; i < prices.length; i++) {
            preMoney = Math.max(prices[i]-prePro,preMoney);
            prePro = Math.min(prePro,prices[i]);
        }
        return preMoney;
    }
    public static void main(String[] args) {
        int[] a = {2, 2, 2, 2, 2};
    }
}
